All of the material in this patent application is subject to copyright protection under the copyright laws of the United States and of other countries. As of the first effective filing date of the present application, this material is protected as unpublished material. However, permission to copy this material is hereby granted to the extent that the copyright owner has no objection to the facsimile reproduction by anyone of the patent documentation or patent disclosure, as it appears in the United States Patent and Trademark Office patent file or records, but otherwise reserves all copyright rights whatsoever.
Not Applicable
1. Field of the Invention
The invention relates to a Soft Output Viterbi Algorithm. More particularly, the invention is a simplified method and apparatus for more easily computing and providing bit reliabilities in combination with a Viterbi algorithm on a processing unit.
2. The Prior Art
The Viterbi algorithm is used for detecting data possibly corrupted by noise in movement of data through communications or recording systems. The algorithm computes the most likely sequence written on the recording given the received noisy data. The output is consistent with some constraints on the sequences that are allowed to be written.
a. Ordinary SOVA
A channel trellis is a diagram defined by states and branches that describes the xe2x80x9cidealxe2x80x9d sequence of outputs to a sequence of inputs. For instance, an Inter-Symbol Interference (ISI) channel trellis, determined by a linear channel impulse response such as Partial Response Class 4 (PR4), Extended Partial Response Class 4 (EPR4) or Extended2 Partial Response Class 4 (E2PR4) describes the ideal response of such a channel to any possible sequence of binary Non-Return to Zero (NRZ) inputs.
For simplicity, an assumption is made that the trellis is a possibly xe2x80x9cprunedxe2x80x9d version of a standard ISI channel trellis diagram with memory v. The states are binary v-tuples, and for u=0 or 1, there is a branch from state (xxe2x88x92v . . . xxe2x88x921) to (xxe2x88x92v+1 . . . xxe2x88x921u). Each branch has an input label (u) and output label (the ideal channel response to the input sequence (xxe2x88x92v . . . xxe2x88x921u).
The xe2x80x9cpruningxe2x80x9d may be the consequence of a constraint (such as MTR) on the channel inputs designed to improve the performance of the detection process.
If the channel detector is designed to pass soft information to a code whose codewords are in some domain other than NRZ (e.g., NRZI, PR4), then the approach described here could be modified accordingly.
Naturally, an assumption is made that the ideal sequence of channel outputs is corrupted by a noise source. The Bahl, Cocke, Jelinek, Raviv (BCJR) algorithm, produces exact a posteriori probabilities (APP) for each bit, assuming that the noise is uncorrelated and data-independent (for instance, Additive White Gaussian Noise (AWGN)). These APP probabilities can be used as soft-decision inputs passed on to other modules in the detection/decoding process, such as a turbo decoder or low density parity check (LDPC) decoder.
Experimental results on test-stand data show that the BCJR algorithm, in conjunction with low density parity check codes, performs quite wellxe2x80x94in spite of the fact that the test-stand noise is typically correlated and data-dependent. But the complexity of the BCJR algorithm may prove too costly for implementation.
SOVA (soft output Viterbi algorithm) is a method for producing approximate APP""s at a lower computational cost than BCJR. The estimates produced by SOVA are based on Viterbi margins (i.e., differences between the metric of a survivor path and its non-surviving path in the Viterbi algorithm). SOVA was introduced by Hagenauer and Hoeher in xe2x80x9cA Viterbi Algorithm with Soft Decision Outputs and its Applicationsxe2x80x9d, Proceedings of Globecom, 1989, pp. 1680-1686.
b. Description of Algorithm
SOVA begins with an ordinary run of the Viterbi algorithm on a long block (of length N) of data. The branch metrics are ordinarily determined by the received channel sample rj and the ideal channel output w on the branch: ∥rjxe2x88x92w∥2; but prior information from previous LDPC iterations may be incorporated in the branch metrics (by adding a term of the form log p where p is the prior probability that the j-th data bit equals the branch input label).
At each bit position j, in between 1 and N, the Viterbi algorithm computes and outputs a detected data bit xj. As is well known this requires a delay equal to the so-called path memory, denoted M (typically, N will be much larger than M). SOVA requires an additional delay, denoted xcex94, within which one makes use of Viterbi margins.
At bit position j, after a delay of xcex94+M, the Viterbi detector will have detected data bits in positions up to j+xcex94. For each k=j+1, . . . , j+xcex94, the detected path up to position k will be a survivor path. As such, it will have at most one non-surviving (runner-up) path ending at the same state (it may have no such paths if the trellis has been pruned). Call this non-surviving path pk, and let mk denote the Viterbi margin (i.e., the difference between the metric of the detected path up to time k and the metric of Pk) The algorithm is concerned only with those pk that would result in a different value for the j-th data bit, i.e.
(pk)jxe2x89xa0xj. 
Such a k is called j-qualified. So, for bit position j, Viterbi margins are computed only for those k that are j-qualified. FIG. 1 illustrates a non-surviving path pk (100) for a j-qualified k as described in the prior art.
For the j-th bit position SOVA will output       ω    j    =                    (                  -          1                )                    X        j              ⁢                  min        k            ⁢              m        k            
where the minimum runs over all j-qualified k such that j+1xe2x89xa6kxe2x89xa6j+xcex94. As shown in J. Hagenauer and E. Offer and L. Papke, xe2x80x9cIterative Decoding of Binary Block and Convolutional Codesxe2x80x9d, IEEE Transactions on Information Theory, March, v.42, 1996, pp 429-445, this quantity is an approximation to the true APP log-likelihood:       ω    j    ≈      log    ⁢          (                        P          (                                                    x                j                            ⁢                              "LeftBracketingBar"                                  r                  j                                                      )                                    P          (                                                                      x                  _                                j                            ⁢                              "LeftBracketingBar"                                  r                  j                                                      )                              )      
where rj denotes the received sequence of samples up to time j+xcex94+M and {overscore ("khgr"j)}, denotes the binary complement of "khgr"j.
c. Access to the non-surviving path pk 
FIG. 2 illustrates a Soft Output Viterbi Algorithm Decoder (200) as described in the prior art. Signals are input into the decoder (200) from a channel (202). The signals pass through an equalizer (204) and into the primary decoding stages of the SOVA. The non-surviving path pk could be obtained from the Viterbi detector with a delay of time M. But then each state s and each i=1, I . . . , M, would require an enormous buffer to store all the non-surviving paths ending at state s at time slot k-i.
An alternative would be to use a second Viterbi detector (212), V2, operating with delay M (210) with respect to the first Viterbi detector (206), V1. Then V1 (206) would provide the detected data path with delay M (210), and V2 (212) would provide the non-surviving path pk. This is described as follows.
First, a buffer is needed, detected buffer (208) DB in FIG. 2, to store the last xcex94 detected bits: xkxe2x88x92xcex94+1 . . . xk. At time slot k+M, this buffer is updated by shifting one unit to the left and filling in the right-most position with the newly detected bit xk from V1 (206). If xcex94xe2x89xa7v (i.e., the look-ahead is at least as large as the channel trellis memory), then the ending state sk of the detected path can be read directly from DB (208) and fed to V2 (212). The differences between the Viterbi detectors V1 (206) and V2 (212) are:
1xe2x80x94V2 (212) has path memory xcex94 instead of M.
2xe2x80x94At time slot k+M, V2 (212) computes all survivor paths ending at bit position k instead of k+M.
In all other respects, V2 (212) operates exactly the same as V1 (206).
In the trellis, state sk has at most two incoming branches. The initial states of these branches are called s and sxe2x80x2. As usual, V2 (212) will add the branch metrics to the current state metrics of s and sxe2x80x2 in order to determine the survivor path at state sk. One of these will be the detected path, and the other will be the non-surviving path pk. Of course, V2 (212) will have access to DB (208) and therefore to the identity of state sk as shown in FIG. 2.
Then V2 (212) will pass the margin mk, at state sk, as well as the last xcex94 bits of the non-surviving path, (pk)j, j=kxe2x88x92xcex94+1, . . . , k, to the qualification/minimization (QM 214) module, which also requires access to the buffer DB (208) of detected bits and an accumulated minimum margin buffer (AMMB 216). At any given time instant k, this module finds the bit positions j for which k is j-qualified and iteratively computes the margins mk, the minimum margin xcfx89 and ultimately the soft outputs.
c. Pseudo-Code for Computation of Soft-Output
Fork=1, . . . , N,{
obtain detected bit xk from Viterbi detector;
xcexck=1000;
d. Complexity
The overhead required by SOVA, above and beyond that required by the Viterbi detector V1, comprises the following:
1xe2x80x94A second Viterbi detector V2 with path memory xcex94.
2xe2x80x94A detection buffer (DB) to hold the detected bits xkxe2x88x92xcex94+1 . . . xk.
3xe2x80x94xcex94xe2x88x921 comparisons per bit in the qualification/minimization module.
4xe2x80x94An accumulated minimum margin buffer (AMMB) to hold the accumulated minimum margins xcexckxe2x88x92xcex94+1 . . . xcexck.
For a 64-state channel trellis, with M=xcex94=64, the number of additions and multiplications for SOVA will be double that of ordinary Viterbi detection and the number of comparisons with be triple that of Viterbi detection. Also, the additional buffers will make the storage requirements somewhat more than double that of Viterbi detection. In addition, SOVA will produce soft outputs with double the latency that the Viterbi algorithm produces hard decisions.
e. Other Prior Art
Further, other related prior art includes Hagenauer""s paper, a patent application filed on Oct. 27, 1999, Attorney Docket No. CH19990112, xe2x80x9cMethod and Apparatus for Encoding and Detection/Decoding of MTR/Parity Codesxe2x80x9d, by Cideciyan et al., and U.S. Pat. No. 5,949,831, xe2x80x9cMethod and Apparatus for Data Detection for PRML Data Channelsxe2x80x9d, by Coker et al., filed May 21, 1997, issued Sep. 7, 1999. These references use error filters to determine if the output reliability crosses some threshold or if parity is violated in a transmission or recording. Here, each filter corresponds to a most likely error which is corrected using an error correction scheme applied to a sequence of symbols or bits.
Also, H. Sawaguchi and S. Mita describe a method for decoding using concatenated error correction in xe2x80x9cSoft-output decoding for concatenated error correction in high-order PRML channels,xe2x80x9d ICC, 1999, pp. 1632-1637.
Accordingly, what is needed is an improved system and method that is not as complex as a BCJR or the ordinary SOVA algorithm and yet accurately produces bit reliabilities. The present invention addresses such a need.
This invention is not a variation of a Viterbi Algorithm itself, rather, the invention is a Viterbi algorithm combined with the use of error filter outputs to produce bit reliabilities.
Thus, the present invention is a SOVA-like method using error filters to reduce the complexity of bit reliability determination further than that of the ordinary SOVA method.
Error patterns corresponding to each of a handful of dominant i.e., most common error patterns, are determined from experimental data. Error filters determine likelihoods of each postulated error pattern. The filters, typically six or seven of them, resolve most of the errors thereby simplifying computation dramatically. The filters do not do general error correction, rather, the error filters compute likelihoods of the most likely error-causing events and are combined to provide bit reliability estimates.